#include <iostream>
#include <vector>

void merge(std::vector<int>& list, int left, int mid, int right)
{
    int start0 = left;
    int start1 = mid + 1;
    std::vector<int> dst = list;
    int idx = left;
    while(start0<=mid || start1<=right)
    {
        if(start0<=mid && start1<=right)
        {
            if(list[start0] < list[start1])
                dst[idx++] = list[start0++];
            else
                dst[idx++] = list[start1++];
        }
        else if(start0<=mid && start1>right)
            dst[idx++] = list[start0++];
        else if(start1<=right && start0>mid)
            dst[idx++] = list[start1++];
    }
    list = dst;
}

void merge_sort(std::vector<int>& list, int left, int right)
{
    if(left >= right)
        return;
    int mid = (left+right) / 2;
    merge_sort(list, left, mid);
    merge_sort(list, mid+1, right);
    merge(list, left, mid, right);
}

int main()
{
    std::vector<std::vector<int>> list = {
        {},
        {1},
        {1,2},
        {2,1},
        {1,2,3,4},
        {4,3,2,1},
        {4,2,3,1},
        {4,3,1,2,5}
    };

    for(int i = 0; i < list.size(); i++)
    {
        for(auto v : list[i])
            std::cout << v << " ";
        
        merge_sort(list[i], 0, list[i].size()-1);

        std::cout << " --> ";
        for(auto v : list[i])
            std::cout << v << " ";
        std::cout << std::endl;
    }

    return 0;
}